package com.sise.DP;

import java.util.Arrays;

/**
 *      DP：动态规划法 (Dynamic Programming,DP)
 *
 *      1、状态：
 *      2、选择：
 *      3、状态转移方程：
 *      4、base case
 *
 *      动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如统计方案数的问题，它们都存在一定的递推性质。
 *      前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，
 *      后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。
 *
 */
public class DP {

    /**
     *      322. 零钱兑换
     *      给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
     *      如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。
     *
     *      输入：coins = [1, 2, 5], amount = 11
     *      输出：3
     *      解释：11 = 5 + 5 + 1
     *
     */

    /**
     *      题解一：暴力递归
     *
     *      1、状态： 目标金额 amount。 状态会随着 选择而改变，例如一开始金额为 11，后续的递归函数中金额可能为 6,9,10
     *      2、选择： conis 数组中列出的所有硬币面额。 例如选择 1,2,5 的硬币
     *      3、函数的定义： 凑出总金额 amount，至少需要 coinChange(coins, amount) 枚硬币
     *      4、base case： amount == 0 时，需要 0 枚硬币； amount < 0 时，不可能凑出
     *
     *      转移方程： 将大问题拆分为三个相同结构的子问题
     *      coinChange([1,2,5], 11) =
     *          min( coinChange([1,2,5], 10), coinChange([1,2,5], 9), coinChange([1,2,5], 6)) + 1
     *
     */
    public int coinChange(int[] coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        int res = Integer.MAX_VALUE;        // 定义返回结果
        for (int coin: coins){              // 将大问题拆分为三个子问题，再通过 Math.min() 取得最小值
            // 计算子问题的结果
            int subProblem = coinChange(coins, amount - coin);
            if (subProblem == -1) continue;         // 子问题无解，跳过
            res = Math.min(res, subProblem) + 1;    // 在子问题中选择最优解，然后加一
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     *      解法二：备忘录 (自顶向下)
     *      由于解法一中的暴力递归有大量的重复动作，故此可以使用备忘录记录数据
     *      在进行 for 循环之前，先查找 memo 中是否已经存在此值，同时判断是否为有效值
     */
    int[] memo;                         // 备忘录
    public int coinChange_2(int[] coins, int amount) {
        memo = new int[amount + 1];     // 记录每一种金额的最小硬币个数
        Arrays.fill(memo, -666);    // memo 数组全部初始化为特殊值
        return dp(coins, amount);
    }

    private int dp(int[] coins, int amount) {
        // base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;

        // 查找备忘录，防止重复计算 (比 暴力破解 多了这一步)
        if (memo[amount] != -666) return memo[amount];

        int res = Integer.MAX_VALUE;
        for (int coin : coins){
            int subProblem = dp(coins, amount - coin);  // 计算子问题的结果
            if (subProblem == -1) continue;                     // 子问题无解则跳过
            res = Math.min(res, subProblem + 1);
        }
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;   // 把计算结果存入备忘录
        return memo[amount];
    }

    /**
     *      解法三：自底向上迭代（自底向上采用了 dp 数组）
     *
     *      1、在 dp[] 数组中，状态是索引（自底向上）    dp数组定义：凑出金额 i，至少需要 dp[i]枚硬币
     *         详解：在 dp[] 中，i = amount，故此索引代表的是 金额，也就是状态。而 dp[] 的值为 最小硬币个数
     *      2、在递归函数中，状态是参数（自顶向下）       函数定义：凑出 amount，至少需要 coinChange(amount)枚硬币
     *      3、其实就是把 递归函数 转换为 dp[]
     */
    public int coinChange_3(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        Arrays.fill(dp, amount + 1);                    // 初始化为特殊值，因为最大值为 amount 枚硬币

        // base case
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++){                // 外层 for 循环在遍历所有状态的所有取值。i=amount : 0~length
            for (int coin : coins){                         // 内层 for 循环在求所有选择的最小值。
                if (i - coin < 0) continue;                 // 子问题无解，跳过
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);  // 状态转移。由于 dp 自底向上，故此 dp[i - coin] 拥有备忘录的功能
            }
        }
        // 看看金额 amount 能不能凑出来
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}
